//package temp.杂难.构造二叉树;
//
////给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并
////返回其根节点。
////
////
////
//// 示例 1:
////
////
////输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
////输出: [3,9,20,null,null,15,7]
////
////
//// 示例 2:
////
////
////输入: preorder = [-1], inorder = [-1]
////输出: [-1]
////
////
////
////
//// 提示:
////
////
//// 1 <= preorder.length <= 3000
//// inorder.length == preorder.length
//// -3000 <= preorder[i], inorder[i] <= 3000
//// preorder 和 inorder 均 无重复 元素
//// inorder 均出现在 preorder
//// preorder 保证 为二叉树的前序遍历序列
//// inorder 保证 为二叉树的中序遍历序列
////
////
//// Related Topics 树 数组 哈希表 分治 二叉树 👍 1921 👎 0
//
//import temp.二叉树.TreeNode;
//
///**
// * 从前序与中序遍历序列构造二叉树
// *
// * @author saint
// */
//class P105_ConstructBinaryTreeFromPreorderAndInorderTraversal {
//    public static void main(String[] args) {
//        Solution solution = new P105_ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();
//
//    }
//
//    //leetcode submit region begin(Prohibit modification and deletion)
///**
// * Definition for a binary tree node.
// * public class TreeNode {
// *     int val;
// *     TreeNode left;
// *     TreeNode right;
// *     TreeNode() {}
// *     TreeNode(int val) { this.val = val; }
// *     TreeNode(int val, TreeNode left, TreeNode right) {
// *         this.val = val;
// *         this.left = left;
// *         this.right = right;
// *     }
// * }
// */
//class Solution {
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        //preOrder第一个点为根节点，在中序遍历中找到这个点，左边为左子树，右边为右子树
//        TreeNode root = new TreeNode(preorder[0]);
//        int inIndex = findIndex(inorder, root.val);//该节点左边为左子树，右边为右子树
//        int preIndex = findIndex(preorder,inorder[inIndex-1]);
//        root.left = buildTree(preorder,inorder,1,preIndex,0,inIndex-1);
//        root.right = buildTree(preorder,inorder,preIndex+1,preorder.length-1,inIndex+1,inorder.length-1);
//    }
//    public TreeNode buildTree(int[] preorder, int[] inorder,int preLeft,int preRight,int inLeft, int inRight){
//        if(!(preLeft<=preRight)||!(inLeft<=inRight)){
//            return null;
//        }
//        TreeNode node = new TreeNode(preLeft);
//        int inIndex = findIndex(inorder, node.val);
//        int preIndex = findIndex(preorder,inorder[inRight-1]);
//        node.left=buildTree(preorder,inorder,preLeft+1,preIndex,inLeft,inIndex-1);
//        node.right = buildTree(preorder,inorder,preRight+1,pre)
//    }
//    public int findIndex(int[] nums,int target){
//        int left=0;
//        int right = nums.length-1;
//        while (left<=right){
//            int mid = (left+right)>>1;
//            if(nums[mid] == target){
//                return mid;
//            }
//            else if (nums[mid]<target){
//                left = mid+1;
//            }
//            else if(nums[mid]>target){
//                right=mid-1;
//            }
//        }
//        return -1;
//    }
//}
////leetcode submit region end(Prohibit modification and deletion)
//
//}
